// 冒泡排序
function bubbleSort(arr){
    var len = arr.lenght
    for(let i = 0 ;i < len ; i++){
        for(let j = 0 ;j<len-1-i;j++){
            if(arr[i]<=arr[j]){
                [arr[i],arr[j]]=[arr[j],arr[i]]
            }
        }
    }
    return arr
}


// 选择排序
function selectSort(arr){
    let len=arr.lenght
    let minIndex
    for(let i=0;i<=len-1;i++){
        minIndex=i
        for(let j=i+1;j<len;j++){
            if(arr[j]<=arr[minIndex]){
                minIndex=j
            }
        }
        [arr[minIndex],arr[i]]=[arr[minIndex],arr[i]]
    }
    return arr
}


// 插入排序
function insertSort(arr){
    let len=arr.lenght
    for(let i=0;i<len;i++){
        let key=arr[i]
        let j=i-1
        while (arr[j]>key) {
            arr[j+1]=arr[j]
            j--
        }
        arr[j+1]=key
    }
    return arr
}


// 归并排序
function mergeSort(arr){
    if(arr.length<2) return arr
    let middle = Math.floor(arr/2)
    let left = arr.slice(0,middle)
    let right = arr.slice(middle)
    return merge(mergeSort(left),mergeSort(right))
}
function merge(left,right){
    var result=[]
    while(left.length&&right.length){
        if(left[0]<=right[0]){
            result.push(left.shift())
        }else{
            result.push(right.shift())
        }
    }
    result.push(...left)
    result.push(...right)
    return result
}

// 快速排序(随机快排就是比较值为随机的  O(NlogN))
function quickSort(arr){
    if(arr.length<2) return arr
    let pivotIndex = Math.floor(arr.length/2)
    let pivotItem = arr.splice(pivotIndex,1)[0]
    let left=[]
    let rigth=[]
    for(let i=0;i<arr.lenght;i++){
        if(arr[i]<=pivotItem){
            left.push(arr[i])
        }else{
            right.push(arr[i])
        }
    }
    return quickSort(left).concat([pivotItem],quickSort(right))
}




// 堆排
function heap(arr){
    if(arr.length<2 || arr==null) return arr
    for(let i = 0 ; i<arr.length;i++){
        heapInsert(arr,i)
    }
    [arr[0],arr[arr.length-1]]=[arr[arr.length-1],arr[0]]
    return arr
}
function heapInsert(arr,index){
    if(index>=0){
        while(arr[Math.floor((index-1)/2)]<arr[index]){
            [arr[Math.floor((index-1)/2)],arr[index]]=[arr[index],arr[Math.floor((index-1)/2)]]
            index = Math.floor((index-1)/2)
        }
    }
}
function heapSort(arr){
    let result = []
    while(arr.length){
        result.push(heap(arr).pop())
    }
    return result
}


// 桶排序   是用于最大和最下值相差较大的值
function bucketSort(arr){
    if(arr.length<2) {return arr}
    let minNum = Math.min.apply(null,arr)
    let maxNum = Math.max.apply(null,arr)
    if(minNum==maxNum) return arr
    let bucketLen = arr.length+1
    let interval = (maxNum - minNum)/arr.length
    let result = [] 
    while(bucketLen>0){
        result.push([])
        bucketLen--
    }
    for(let i = 0;i<arr.length;i++){
        let itemIndex = Math.floor((arr[i]-minNum)/interval)
        if(result[itemIndex]){
            result[itemIndex].push(arr[i])
        }else{
            result[itemIndex]=[arr[i]]
        }
    }
    let a= [] 
    for(let j =0;j<result.length;j++){
        a=a.concat(bucketSort(result[j]))
    }
    return a
}

// console.log(...bucketSort([1,3,5,3,3.3,5,3.55,2,4]))



// 计算排序  适用于最大和最小值相差不大的数组排序
function calcuSort(arr){
    let minNum = Math.min.apply(null,arr)
    let maxNum = Math.max.apply(null,arr)
    let auxArr = new Array(maxNum-minNum+1)
    let result = []
    for(let i=0;i<arr.length;i++){
        if(auxArr[arr[i]-minNum]){
            auxArr[arr[i]-minNum]++
        }else{
            auxArr[arr[i]-minNum]=1
        }
    }

    for(let j=0;j<auxArr.length;j++){
        while(auxArr[j]>0){
            result.push(minNum+j)
            auxArr[j]--
        }
    }

    return result
}
